package Sort;

/**
 * 一种插入排序
 * 对下标按一定增量分组 每组使用插入
 * lenth/2 为间隔 （或其他）
 */
public class ShellSort {
    public static void main(String[] args) {
        int arr[] = {8, 9, 7, 1, 2, 3, 4, 5, 8, 3, 4, 2, 1, 0};
        shellSort(arr);
    }

    public static int[] shellSort(int[] arr) {
        //增量gap 并逐步的减少增量 也就是分组
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            //从第gap个元素 ，组个对其所在的组进行直接插入排序 第二步 遍历  通过差值找组内元素
            for (int i = gap; i < arr.length; i++) {
                int j = i;
                //把当前i （j）的位置的值 记录成temp
                int temp = arr[j];
                //如果出现后比前大
                if (arr[j] < arr[j - gap]) {
                    //寻找插入的位置
                     while (j - gap >= 0 && temp < arr[j - gap]) {
                        //移动 ，看当前位置应该移动到哪 有可能是直接-gap 或 -2gap 一个个比较
                        arr[j] = arr[j - gap];
                        j -= gap;
                    }
                    //退出while循环后说明已经找到了位置
                    arr[j] = temp;
                }

            }
        }
        return arr;
    }



    public static int[] shellSort3(int[] arr) {
        //增量gap 并逐步的减少增量 也就是分组
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                int j = i;
                int temp = arr[j];
                while (arr[j] < arr[j - gap] && j - gap > 0) {
                            arr[j]=arr[j-gap];
                            j-=gap;
                }
                arr[j]=temp;

            }
        }
        return arr;

    }
}
